package leetcode.cn;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * @version 1.8
 * @Author Djx_hmbb
 * @Date 2023/11/22 23:11
 * @注释:438.找到字符串中所有字母异位词
 */
public class FindAnagrams {
    /*给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。*/

    public static List<Integer> findAnagrams(String s, String p) {
        HashMap<Character,Integer> hash1 = new HashMap<>();
        HashMap<Character,Integer> hash2 = new HashMap<>();
        char[] pp = p.toCharArray();
        //将p中的字符存入hash表中
        for (char c : pp) {
            hash1.put(c, hash1.getOrDefault(c, 0) + 1);
        }
        int n = pp.length;//记录了p的长度
        char[] ss = s.toCharArray();
        int left = 0,right = 0;
        List<Integer> list = new LinkedList<>();
        while(right<ss.length){
            //进窗口
            hash2.put(ss[right], hash2.getOrDefault(ss[right++],0) + 1);
            //判断hash2的长度
            if(hash2.size()>n){
                //如果hash2的长度>n，右移，左移
                hash2.put(ss[right],hash2.getOrDefault(ss[right],0)+1);
                hash2.put(ss[left],hash2.get(ss[left])-1);
                if(hash2.get(ss[left]) <=0 ){
                    hash2.remove(ss[left++]);
                }
            }
            int m = 0;
            if(hash2.size() == n){
                for (int i = 0; i < n; i++) {
                    if(hash2.containsKey(hash1.get(pp[i])) && hash2.containsValue(hash1.containsValue(hash1.get(pp[i])))){
                        //如果hash2中存在hash1中的字符，并且hash2中对应的个数相同,则记录left的值
                        list.add(left);
                    }
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        String s = "abab";
        String p = "ab";
        List<Integer> list = findAnagrams(s,p);
        System.out.println(list);
    }
}
